/**
 *  @file    DeleteScope.c
 *  @brief   在带头结点（或普通链表）的无序单链表中，删除所有
 *           数据值落在给定闭区间 [left, right] 内的节点
 *  @details 示例演示了链表的创建、头插/尾插、按区间删、打印等基础操作，
 *           并着重讲解“删除区间元素”算法的实现要点。
 *  @author  WangBlue (wangjiping596@gmail.com)
 *  @date    2025‑07‑02 14:34
 *  @version 1.0
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>   // 若后续扩展布尔函数接口，可使用

// ------------------------- 节点结构定义 -------------------------

/**
 * @brief 单链表节点结构体
 */
typedef struct node {
    int           data;   ///< 数据域
    struct node  *next;   ///< 指针域：指向下一个节点
} node, *link;            ///< link 为 node* 类型别名，书写简洁

// ------------------------- 创建节点 -------------------------

/**
 * @brief 申请并初始化一个新节点
 * @param value  节点要保存的整数值
 * @return 成功返回新节点指针；若内存分配失败返回 NULL
 */
link createNode(int value) {
    link newNode = (link)malloc(sizeof(node));  // 申请节点内存
    if (newNode == NULL) return NULL;           // 分配失败，及时返回

    newNode->data = value;                      // 赋值
    newNode->next = NULL;                       // 尾指向 NULL
    return newNode;
}

// ------------------------- 头插法 -------------------------

/**
 * @brief 头插法在 *head 处插入新节点
 * @param head   指向链表头指针的指针（允许修改头指针本身）
 * @param value  要插入的数据
 * @note  复杂度 O(1)
 */
void insertHead(link *head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;                // 内存不足直接返回

    newNode->next = *head;                      // 新节点指向原头
    *head = newNode;                            // 更新头指针
}

// ------------------------- 尾插法 -------------------------

/**
 * @brief 尾插法在链表尾部追加新节点
 * @param head   指向链表头指针的指针
 * @param value  要插入的数据
 * @note  复杂度 O(n)，若维护 tail 指针可优化为 O(1)
 */
void insertTail(link *head, int value) {
    link newNode = createNode(value);
    if (newNode == NULL) return;

    // 1. 链表为空：新节点即为头节点
    if (*head == NULL) {
        *head = newNode;
        return;
    }

    // 2. 链表非空：遍历到末尾
    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = newNode;                        // 挂到尾部
}

// ------------------------- 打印链表 -------------------------

/**
 * @brief 顺序打印链表中所有节点数据
 * @param head  链表头指针
 */
void printList(link head) {
    if (head == NULL) return;                   // 空链表直接返回

    link cur = head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
}

// ------------------------- 区间删除核心算法 -------------------------

/**
 * @brief 删除链表中所有值落在 [left, right] 闭区间内的节点
 * @param head   指向链表头指针的指针
 * @param left   区间左端点 (含)
 * @param right  区间右端点 (含)
 * @note
 *   1. 支持删除连续、多段、甚至整表节点
 *   2. 时间复杂度 O(n)，空间复杂度 O(1)
 *   3. 采用 **双指针 pre / cur**：pre 指向待检查节点 cur 的前驱
 */
void deleteScope(link *head, int left, int right) {
    if (*head == NULL) return;                  // 空链表

    /* --- 第 1 步：处理可能需要删除的 “首部连续区间” --- */
    while (*head != NULL &&
           (*head)->data >= left && (*head)->data <= right) {
        link temp = *head;                      // 记录待删节点
        *head = (*head)->next;                  // 头指针后移
        free(temp);                             // 释放内存
    }

    /* 若链表被删空，直接返回 */
    if (*head == NULL) return;

    /* --- 第 2 步：常规遍历删除，其余节点保证 cur != NULL --- */
    link pre = *head;
    link cur = (*head)->next;

    while (cur != NULL) {
        if (cur->data >= left && cur->data <= right) {
            /* 命中删除区间：跳过 cur 并释放 */
            pre->next = cur->next;              // 重连
            free(cur);                          // 释放
            cur = pre->next;                    // cur 前进（pre 不动）
        } else {
            /* 不删除：双指针同步后移 */
            pre = cur;
            cur = cur->next;
        }
    }
}

// ------------------------- 主函数（示例） -------------------------

/**
 * @brief 测试区间删除功能
 */
int main() {
    link head = NULL;   // 初始化空链表

    /* 构造链表：2 → 4 → 5 → 3 → 0 → 1 */
    insertHead(&head, 1);
    insertHead(&head, 0);
    insertHead(&head, 3);
    insertHead(&head, 5);
    insertHead(&head, 4);
    insertHead(&head, 2);

    /* 删除 [0, 3] 区间内的节点：将删除 2,3,0,1 */
    deleteScope(&head, 0, 3);

    /* 预期剩余链表：4 → 5 */
    printList(head);

    return 0;
}
